

#include "bitmap.h"


inline void BITMAP_EX_Exchange(KIND_BITMAP_MATCH_S* pstKindMatchArray, unsigned int uiSrcPos, unsigned int uiDestPos)
{
    KIND_BITMAP_MATCH_S stKindBitmap = pstKindMatchArray[uiSrcPos];
    pstKindMatchArray[uiSrcPos] = pstKindMatchArray[uiDestPos];
    pstKindMatchArray[uiDestPos] = stKindBitmap;
}

inline unsigned int BITMAP_EX_SearchAndWalk(KIND_BITMAP_MATCH_S* pstKindBitmap, unsigned int uiBitmapLoc, unsigned int* puiValue)
{
    unsigned int uiLoop;
    unsigned int uiCurrentLoc = BITMAP_LOC_INVALID;
    unsigned int uiCurrentValue = 0;
    unsigned int uiNextLoc = BITMAP_LOC_INVALID;
    unsigned int uiNextValue = 0;
    unsigned int uiResultLoc = BITMAP_LOC_INVALID;
    unsigned int uiBitmapSubCnt = pstKindBitmap->uiBitmapSubCnt;
    BITMAP_MATCH_EX_S* pstSubBitmap = pstKindBitmap->astSubBitmap;

    for (uiLoop = 0; uiLoop < uiBitmapSubCnt; uiLoop++)
    {
        while (1)
        {
            if (0 != pstSubBitmap->pstBitmap->uiValue)
            {
                if (pstSubBitmap->pstBitmap->uiLoc > uiBitmapLoc)
                {
                    if (pstSubBitmap->pstBitmap->uiLoc < uiNextLoc)
                    {
                        uiNextLoc = pstSubBitmap->pstBitmap->uiLoc;
                        uiNextValue = pstSubBitmap->pstBitmap->uiValue;
                    }
                    else if (pstSubBitmap->pstBitmap->uiLoc == uiNextLoc)
                    {
                        uiNextValue |= pstSubBitmap->pstBitmap->uiValue;
                    }
                    break;
                }
                else if (pstSubBitmap->pstBitmap->uiLoc < uiBitmapLoc)
                {
                    pstSubBitmap->pstBitmap++;
                }
                else
                {
                    uiCurrentLoc = uiBitmapLoc;
                    uiCurrentValue |= pstSubBitmap->pstBitmap->uiValue;
                    pstSubBitmap->pstBitmap++;
                }
            }
            else
            {
                break;
            }
        }
        pstSubBitmap++;
    }

    if (BITMAP_LOC_INVALID != uiCurrentLoc)
    {
        uiResultLoc = uiCurrentLoc;
        *puiValue = uiCurrentValue;
    }
    else
    {
        uiResultLoc = uiNextLoc;
        *puiValue = uiNextValue;
    }
    
    return uiResultLoc;
}

/*
uiMinKindPos
...
uiMaxKindPos
*/
unsigned int BITMAP_EX_First_CompareOpt(KIND_BITMAP_MATCH_S* pstKindMatchArray, unsigned int uiKindCount,
    unsigned int uiMinKindPos, unsigned int uiMaxKindPos, unsigned int auiResult[RESULT_COUNT_MAX])
{
    unsigned int uiKindLoop;
    unsigned int uiBitmapLoc;
    unsigned int uiBitmapLocEx;
    unsigned int uiBitmapValueEx;
    unsigned int uiCurrentLoc = 0;
    unsigned int uiCurrentValue;
    KIND_BITMAP_MATCH_S* pstBaseKindBitmap;

    if (uiMinKindPos != uiMaxKindPos)
    {
        if (0 != uiMinKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, 0, uiMinKindPos);
        }
        if (0 == uiMaxKindPos)
        {
            uiMaxKindPos = uiMinKindPos;
        }
        if ((uiKindCount - 1) != uiMaxKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, (uiKindCount - 1), uiMaxKindPos);
        }
    }

    pstBaseKindBitmap = &(pstKindMatchArray[0]);
    while (1)
    {
        uiBitmapLoc = BITMAP_EX_SearchAndWalk(pstBaseKindBitmap, uiCurrentLoc, &uiCurrentValue);
        if (BITMAP_LOC_INVALID == uiBitmapLoc)
        {
            // finish
            return 0;
        }

        uiCurrentLoc = uiBitmapLoc;
        for (uiKindLoop = 1; uiKindLoop < uiKindCount; uiKindLoop++)
        {
            uiBitmapLocEx = BITMAP_EX_SearchAndWalk(&(pstKindMatchArray[uiKindLoop]), uiCurrentLoc, &uiBitmapValueEx);
            if (BITMAP_LOC_INVALID == uiBitmapLocEx)
            {
                // finish
                return 0;
            }

            if (uiBitmapLocEx == uiCurrentLoc)
            {
                uiCurrentValue &= uiBitmapValueEx;
                if (0 == uiCurrentValue)
                {
                    uiCurrentLoc++;
                    break;
                }
            }
            else if (uiBitmapLocEx > uiCurrentLoc)
            {
                uiCurrentLoc = uiBitmapLocEx;
                uiCurrentValue = 0;
                break;
            }
            else
            {
                //bug: impossible
                return 0;
            }
        }

        if (0 != uiCurrentValue)
        {
            auiResult[0] = (uiCurrentLoc << 5) + BITMAP_FIRST(uiCurrentValue);
            return 1;
        }
    }

    return 0;
}

/*
uiMinKindPos
uiHeadMaxLocPos
...
uiMaxKindPos
*/
unsigned int BITMAP_EX_First_CompareUltra(KIND_BITMAP_MATCH_S* pstKindMatchArray, unsigned int uiKindCount,
    unsigned int uiMinKindPos, unsigned int uiMaxKindPos, unsigned int uiHeadMaxLocPos, unsigned int auiResult[RESULT_COUNT_MAX])
{
    unsigned int uiKindLoop;
    unsigned int uiBitmapLoc;
    unsigned int uiBitmapLocEx;
    unsigned int uiBitmapValueEx;
    unsigned int uiCurrentLoc = 0;
    unsigned int uiCurrentValue;
    KIND_BITMAP_MATCH_S* pstBaseKindBitmap;

    if (uiMinKindPos != uiHeadMaxLocPos)
    {
        if (0 != uiMinKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, 0, uiMinKindPos);
            if (0 == uiHeadMaxLocPos)
            {
                uiHeadMaxLocPos = uiMinKindPos;
            }
            if (0 == uiMaxKindPos)
            {
                uiMaxKindPos = uiMinKindPos;
            }
        }        
        if (1 != uiHeadMaxLocPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, 1, uiHeadMaxLocPos);
            if (1 == uiMaxKindPos)
            {
                uiMaxKindPos = uiHeadMaxLocPos;
            }
        }
        if ((uiKindCount - 1) != uiMaxKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, (uiKindCount - 1), uiMaxKindPos);
        }
    }
    else if (uiMinKindPos != uiMaxKindPos)
    {
        if (0 != uiMinKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, 0, uiMinKindPos);
            if (0 == uiMaxKindPos)
            {
                uiMaxKindPos = uiMinKindPos;
            }
        }
        if ((uiKindCount - 1) != uiMaxKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, (uiKindCount - 1), uiMaxKindPos);
        }
    }

    pstBaseKindBitmap = &(pstKindMatchArray[0]);
    while (1)
    {
        uiBitmapLoc = BITMAP_EX_SearchAndWalk(pstBaseKindBitmap, uiCurrentLoc, &uiCurrentValue);
        if (BITMAP_LOC_INVALID == uiBitmapLoc)
        {
            // finish
            return 0;
        }

        uiCurrentLoc = uiBitmapLoc;
        for (uiKindLoop = 1; uiKindLoop < uiKindCount; uiKindLoop++)
        {
            uiBitmapLocEx = BITMAP_EX_SearchAndWalk(&(pstKindMatchArray[uiKindLoop]), uiCurrentLoc, &uiBitmapValueEx);
            if (BITMAP_LOC_INVALID == uiBitmapLocEx)
            {
                // finish
                return 0;
            }

            if (uiBitmapLocEx == uiCurrentLoc)
            {
                uiCurrentValue &= uiBitmapValueEx;
                if (0 == uiCurrentValue)
                {
                    uiCurrentLoc++;
                    break;
                }
            }
            else if (uiBitmapLocEx > uiCurrentLoc)
            {
                uiCurrentLoc = uiBitmapLocEx;
                uiCurrentValue = 0;
                break;
            }
            else
            {
                //bug: impossible
                return 0;
            }
        }

        if (0 != uiCurrentValue)
        {
            auiResult[0] = (uiCurrentLoc << 5) + BITMAP_FIRST(uiCurrentValue);
            return 1;
        }
    }

    return 0;
}

unsigned int BITMAP_EX_All_CompareOpt(KIND_BITMAP_MATCH_S* pstKindMatchArray, unsigned int uiKindCount,
    unsigned int uiMinKindPos, unsigned int uiMaxKindPos, unsigned int auiResult[RESULT_COUNT_MAX])
{
    unsigned int uiKindLoop;
    unsigned int uiBitmapLoc;
    unsigned int uiBitmapLocEx;
    unsigned int uiBitmapValueEx;
    unsigned int uiCurrentLoc = 0;
    unsigned int uiCurrentValue;
    unsigned int uiResultCnt = 0;
    unsigned int uiBitPos;
    unsigned int uiTempPos = 0;
    unsigned int uiLastPos = 0;
    KIND_BITMAP_MATCH_S* pstBaseKindBitmap;

    if (uiMinKindPos != uiMaxKindPos)
    {
        if (0 != uiMinKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, 0, uiMinKindPos);
        }
        if (0 == uiMaxKindPos)
        {
            uiMaxKindPos = uiMinKindPos;
        }
        if ((uiKindCount - 1) != uiMaxKindPos)
        {
            BITMAP_EX_Exchange(pstKindMatchArray, (uiKindCount - 1), uiMaxKindPos);
        }
    }

    pstBaseKindBitmap = &(pstKindMatchArray[0]);
    while (1)
    {
        uiBitmapLoc = BITMAP_EX_SearchAndWalk(pstBaseKindBitmap, uiCurrentLoc, &uiCurrentValue);
        if (BITMAP_LOC_INVALID == uiBitmapLoc)
        {
            // finish
            return uiResultCnt;
        }

        uiCurrentLoc = uiBitmapLoc;
        for (uiKindLoop = 1; uiKindLoop < uiKindCount; uiKindLoop++)
        {
            uiBitmapLocEx = BITMAP_EX_SearchAndWalk(&(pstKindMatchArray[uiKindLoop]), uiCurrentLoc, &uiBitmapValueEx);
            if (BITMAP_LOC_INVALID == uiBitmapLocEx)
            {
                // finish
                return uiResultCnt;
            }

            if (uiBitmapLocEx == uiCurrentLoc)
            {
                uiCurrentValue &= uiBitmapValueEx;
                if (0 == uiCurrentValue)
                {
                    uiCurrentLoc++;
                    break;
                }
            }
            else if (uiBitmapLocEx > uiCurrentLoc)
            {
                uiCurrentLoc = uiBitmapLocEx;
                uiCurrentValue = 0;
                break;
            }
            else
            {
                //bug: impossible
                return uiResultCnt;
            }
        }

        if (0 != uiCurrentValue)
        {
            uiTempPos = uiCurrentLoc << 5;
            for (uiBitPos = 0; uiBitPos < 32; uiBitPos++)
            {
                if (BIT_TEST(uiCurrentValue, uiBitPos))
                {
                    uiLastPos = uiTempPos + uiBitPos + 1;
                    auiResult[uiResultCnt] = uiLastPos;
                    uiResultCnt++;
                }
            }
        }
    }

    return uiResultCnt;
}